package primary.code01_Sort;

/**
 * 二分法
 * 1 有序数组，找某个数是否存在
 * 2 有序数组，找大于等于某个数的最左侧
 * 3 无序数组，找局部最小
 */
public class Code05_PartitionSearch {

    /**
     * 1 "有序"数组，找某个数是否存在
     *
     * @param arr
     * @param num
     * @return
     */
    private static int partition1(int[] arr, int num) {
        if (arr == null || arr.length == 0) return -1;
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (arr[m] == num) return m;
            else if (arr[m] < num) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return -1;
    }

    private static int partition1Test(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (arr[m] == num) {
                return m;
            } else if (arr[m] > num) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }

    /**
     * 2 有序数组，找大于等于某个数的最左侧
     *
     * @param arr
     * @param num
     * @return
     */
    private static int partition2(int[] arr, int num) {
        if (arr == null || arr.length == 0) return -1;
        int l = 0;
        int r = arr.length - 1;
        int res = -1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (arr[m] >= num) {
                r = m - 1;
                res = m;//更新可能的结果
            } else l = m + 1;
        }
        return res;
    }

    private static int partition2Test(int[] arr, int num) {
        if (arr == null || arr.length == 0) return -1;
        int l = 0;
        int r = arr.length - 1;
        int res = -1;
        while (r >= l) {
            int m = (l + r) / 2;
            if (arr[m] >= num) {
                res = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return res;
    }

    /**
     * 3 无序数组，找其中一个局部最小
     *
     * @param arr
     * @return
     */
    private static int partition3(int[] arr) {
        if (arr == null || arr.length == 0) return -1;
        if (arr.length == 1) return 0;

        if (arr[0] < arr[1]) return 0;
        if (arr[arr.length - 1] < arr[arr.length - 2]) return arr.length - 1;
        int l = 1;
        int r = arr.length - 2;
        while (l <= r) {
            int m = (l + r) / 2;
            if (arr[m] < arr[m - 1] && arr[m] < arr[m + 1]) return m;
            else if (arr[m] < arr[m - 1]) l = m + 1;
            else r = m - 1;
        }
        return -1;
    }

    private static int partition3Test(int[] arr) {
        if (arr == null || arr.length <= 2) return -1;
        if (arr[0] < arr[1]) return 0;
        if (arr[arr.length - 1] < arr[arr.length - 2]) return arr.length - 1;
        int l = 1;
        int r = arr.length - 2;
        while (l <= r) {
            int m = (l + r) / 2;
            if (arr[m] < arr[m - 1] && arr[m] < arr[m + 1]) {
                return m;
            } else if (arr[m] > arr[m - 1]) {
                r = m - 1;
            } else {
                l = m + 1;
            }

        }
        return -1;
    }

    /**
     * res1 = 7
     * res2 = 10
     * res3 = 6
     */
    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 8, 23, 23, 23, 23, 57, 58, 87, 87, 89, 90, 587};
//        int res1 = partition1(arr, 23);
        int res1 = partition1Test(arr, 23);
        System.out.println("res1 = " + res1);

//        int res2 = partition2(arr, 87);
        int res2 = partition2Test(arr, 86);
        System.out.println("res2 = " + res2);

        int[] arr3 = {100, 90, 87, 90, 57, 8, 1, 587, 689};
//        int res3 = partition3(arr3);
        int res3 = partition3Test(arr3);
        System.out.println("res3 = " + res3);
    }
}
